Super pow

Time: O(N); Space: O(1); medium

Note:

• N is the size of b

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3]

Output: 8

Example2:

Input: a = 2, b = [1, 0]

Output: 1024

class Solution1(object):
    def superPow(self, a, b) -> int:
        """
        :type a: int
        :type b: List[int]
        :rtype: int
        """
        def myPow(a, n, b):
            result = 1
            x = a % b
            while n:
                if n & 1:
                    result = result * x % b
                n >>= 1
                x = x * x % b
            return result % b

        result = 1
        for digit in b:
            result = myPow(result, 10, 1337) * myPow(a, digit, 1337) % 1337

        return result

s = Solution1()
a, b = 2, [3]
assert s.superPow(a, b) == 8
a, b = 2, [1, 0]
assert s.superPow(a, b) == 1024

See also:

https://leetcode.com/problems/super-pow

https://www.lintcode.com/problem/super-pow